\documentclass{article}
\setlength{\parskip}{2.0mm}

\usepackage{listings}
\lstset{
breaklines=true,
basicstyle=\footnotesize,
tabsize=2
}

%\usepackage{a4wide}
\usepackage{listings}
\usepackage{color}
\usepackage{graphicx}
\usepackage{float}
\usepackage{amsmath}
\usepackage{subfig}
\usepackage{cite}
\usepackage{url}
\usepackage{amsmath}

\begin{document}

\title{Robotics - Wavefront Navigation}

\author{Oleg Iegorov, 
\and Jander Nascimento}

\maketitle

\section{Wavefront Algorithm}

Our algorithm to find the shortest path from the goal
position to the start position is based on the classical Dijkstra's
algorithm. The cells of the workspace grid represent the vertices of the
graph and each cell has 4 neighbors at maximum.

Given the goal position we compute the path length to all other cells
of the workspace. Then, the start position is taken and if the path from
start to goal exists, the shortest one is returned.

To calculate the path length from the given cell to all others we have
to maintain an additional array \emph{visited[][]}. It keeps track of
those cells for which the shortest path has been already computed.  A
\emph{navigation[][]} array stores the distance from the goal position for
each cell.

The main algorithm is thus the following:

\begin{lstlisting}[language=C]
visited[goal_x][goal_y] = 1;
navigation[goal_x][goal_y] = 0;
for each neighbor of the goal cell
  put navigation[][] value to 0 + 1;
for each cell in the grid
  current = unvisited cell with min navigation value;
  nav_value = navigation[current_x][current_y];
  visited[current_x][current_y];
  for each neighbor [nx][ny] of this cell
    if (navigation[nx][ny] > nav_value)
      navigation[nx][ny] = nav_value + 1;
\end{lstlisting}

\section{Shortest path selection}

After applying the navigation function, we have a connected graph in which
all the nodes receive the value that represents the distance between
itself and the goal. Thus, as long as the goal do not change, the
navigation function result stays the same.
 
The idea behind the the shortest path selection can be represented in
the equations \ref{eq:neighbor} and \ref{eq:path}. Where given the $x$ and
$y$ coordinates of the start position, we navigate through the graph,
always going towards the neighbor with the smallest value.
(Equation \ref{eq:path}).

Then we perform the same operation in this selected node until the value reached is 0(which represents the cost of our goal).
 
\begin{equation}
 neighbor(x,y)=\{n(x,y+1),n(x,y-1),n(x+1,y),n(x-1,y)\}
\label{eq:neighbor}
\end{equation}

\begin{equation}
 \operatorname{arg\,min}cost(neighbors(x,y)) \forall x,y \in N
\label{eq:path}
\end{equation}


\section{Specification}

The workspace dimension is coded with a 5x6 matrix, which represents the workspace where the navigation function is going to be applied. 

As the workspace is statically written inside the code, it is not
possible to change the workspace without re-compile the code. 

\section{How to Compile \& Run}

To compile the application simply type {\it make} and then run the
application with ./wave.

The code is also available at the address \url{https://code.google.com/p/jfrobotics/source/browse/trunk/wavefront/}.

\end{document}


